package com.dubious.interview.euler;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Utilities {
    /**
     * Find maximum value in a list.
     * 
     * @param values The list to search.
     * @return The maximum value.
     */
    public static Long findMax(List<Long> values) {
        Long maxValue = 0L;
        for (Long value : values) {
            if (value > maxValue) {
                maxValue = value;
            }
        }

        return maxValue;
    }

    /**
     * Find the prime factors of a number.
     * @param value The number to prime factorize.
     * @return The prime factors, in ascending order.
     */
    public static List<Long> primeFactorize(Long value) {
        List<Long> primeFactors = new LinkedList<Long>();
        // find factors and divide
        Long i = 2L;
        while (i <= Math.sqrt(value)) {
            if (value % i == 0) {
                primeFactors.add(i);
                value = value / i;
            } else if (i == 2) {
                i = 3L;
            } else {
                i += 2;
            }
        }
        primeFactors.add(value);
        return primeFactors;
    }
    
    /**
     * Find the divisors of a number.
     * @param value The number for which to find divisors.
     * @return The divisors, in no particular order.
     */
    public static Set<Long> getDivisors(Long value)
    {
        // use the prime factorization
        List<Long> primeFactors = Utilities.primeFactorize(value);
        
        // have a set that tracks all known divisors
        // the set is initialized with 1
        Set<Long> divisors = new HashSet<Long>();
        divisors.add(Long.valueOf(1));
        
        // the set is expanded by iterating over the prime factors 
        // and multiplying each number already in the set by the factor
        for(Long primeFactor : primeFactors)
        {   
            Set<Long> newDivisors = new HashSet<Long>();
            for(Long divisor : divisors)
            {
                newDivisors.add(divisor * primeFactor);
            }
            divisors.addAll(newDivisors);
        }
        
        return divisors;
    }
    

    /**
     * Extract digits from an int into a List.
     * 
     * @param value The value from which to extract digits.
     * @return The digits in an ordered list.
     */
    public static List<Integer> extractDigits(long value)
    {
        List<Integer> digits = new LinkedList<Integer>();
        long currentValue = value;
        while(currentValue > 0)
        {
            digits.add(0, (int)(currentValue % 10));
            currentValue /= 10;
        }
        
        return digits;
    }
    
    /**
     * Extract a sequence of digits from a given list of digits as a number.
     */
    public static long getSubNumber(List<Integer> digits, int beginIndex, int endIndex)
    {
        long value = 0;
        for(int i = 0; i <= endIndex - beginIndex; i++)
        {
            value += digits.get(endIndex - i) * Math.pow(10, i);
        }
        
        return value;
    }

    /**
     * Indicate if the elements in a list are increasing.
     * eg// {3,4,4,5,9}, {1,4,8,9}
     * 
     * @param elements The list to analyze.
     * @return true if increasing, false otherwise.
     */
    public static boolean isIncreasing(List<Integer> elements)
    {
        int lastElement = -1;
        for(Integer element : elements)
        {
            if(element < lastElement)
            {
                return false;
            }
            lastElement = element;
        }
        
        return true;
    }
    
    /**
     * Indicate if the elements in a list are decreasing.
     * eg// {8,5,5,1}, {99,45,19} 
     * @param elements The list to analyze.
     * @return true if decreasing, false otherwise.
     */
    public static boolean isDecreasing(List<Integer> elements)
    {
        int lastElement = 10;
        for(Integer element : elements)
        {
            if(element > lastElement)
            {
                return false;
            }
            lastElement = element;
        }
        
        return true;
        
    }
}
